package com.czk.tree.traverse.pra;

import lombok.Getter;
import lombok.Setter;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author chenzhangkun
 * @ClassName StackTraverse
 * @description: TODO
 * @date 2024年04月28日
 */
public class StackTraverse {
	public static void main(String[] args) {
		Node node4 = new Node(4);
		Node node5 = new Node(5);
		Node node6 = new Node(6);
		Node node7 = new Node(7);
		Node node2 = new Node(2, node4, node5);
		Node node3 = new Node(3, node6, node7);
		Node node1 = new Node(1, node2, node3);
		node1.preTraverse();
		System.out.println("================");
		node1.InOrderTraverse();
		System.out.println("================");
		node1.postTraverse();
	}

}

@Getter
@Setter
class Node {
	private Integer name;
	private Node left;
	private Node right;

	public Node(Integer name, Node left, Node right) {
		this.name = name;
		this.left = left;
		this.right = right;
	}

	public Node(Integer name) {
		this.name = name;
	}

	@Override
	public String toString() {
		return "Node{" +
				"name='" + name + '\'' +
				'}';
	}

	public void preTraverse() {
		Deque<Node> stack = new LinkedList<>();
		stack.push(this);
		while (!stack.isEmpty()) {
			Node pop = stack.pop();
			System.out.println(pop);
			if (pop.right != null) {
				stack.push(pop.right);
			}
			if (pop.left != null) {
				stack.push(pop.left);
			}
		}
	}


	public void InOrderTraverse() {
		Deque<Node> stack = new LinkedList<>();
		Node cur = this;
		while (!stack.isEmpty() || cur != null) {
			// 将左子树一直往stack里面push
			while (cur != null) {
				stack.push(cur);
				cur = cur.left;
			}
			Node node = stack.pop();
			System.out.print(node.name + "\t");
			if (node.right != null) {
				// 将右边往里面push
				cur = node.right;
			}
		}
	}

	public void postTraverse() {

	}
}
